package algorithm_demo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 39. 组合总和
 * <a href="https://leetcode.cn/problems/combination-sum/">https://leetcode.cn/problems/combination-sum/</a>
 * @author Api
 * @date 2023/5/5 1:17
 */
public class Problem_039_CombinationSum {
    List<List<Integer>> list2 = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, 0, 0, target, path);
        return list2;
    }


    public void dfs(int[] nums, int start, int sum, int target, List<Integer> path){
        if(sum == target){
            list2.add(new ArrayList<Integer>(path));
            return;
        }
        //这里的条件sum+nums[i]<=target如果不满足的话，i直接不会++了，不用每次进去在进行判断了
        for(int i = start; (i < nums.length && sum+nums[i] <= target);i++){
            path.add(nums[i]);
            dfs(nums, i, sum+nums[i], target, path);
            //回溯
            path.remove(path.size()-1);
        }
    }
}
